home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / cagdaiso.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  13.4 KB  |  464 lines
  1. /******************************************************************************
  2. * CagdAIso.c - adaptive isoline surface extraction algorithm.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Aug. 92.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. #define CONVEX_BLEND(v1, v2, b1, b2, t) { \
  10.         CagdRType \
  11.             Blend = -b1 / ( b2 - b1 ); \
  12.         t = v2 * Blend + v1 * (1.0 - Blend); \
  13.         }
  14.  
  15. static int MinSubdivLevel = 1;
  16.  
  17. static CagdCrvStruct *CagdAdapIsoExtractAux(int Level,
  18.                      CagdSrfStruct *Srf, CagdSrfStruct *NSrf,
  19.                      CagdCrvStruct *Crv1, CagdCrvStruct *NCrv1,
  20.                      CagdCrvStruct *Crv2, CagdCrvStruct *NCrv2,
  21.                      CagdRType Crv1Param, CagdRType Crv2Param,
  22.                      CagdSrfDirType Dir, CagdRType Eps2,
  23.                      CagdBType FullIso, CagdBType SinglePath);
  24.  
  25. /******************************************************************************
  26. * Sets minimum level of subdivision forced in the adaptive iso extraction.    *
  27. ******************************************************************************/
  28. void CagdSetAdapIsoExtractMinLevel(int MinLevel)
  29. {
  30.     MinSubdivLevel = MinLevel;
  31. }
  32.  
  33. /******************************************************************************
  34. * Extract a valid coverage set of isolines from the given surface in the      *
  35. * given direction and epsilon.                              *
  36. *   If FullIso is TRUE, all extracted isocurves are spanning the entire       *
  37. * parametric domain.                                  *
  38. *   If SinglePath is TRUE, the entire coverage is going to be a single curve  *
  39. *   If NSrf != NULL, every second curve will be a vector field curve rep. the *
  40. * unnormalized normal for the previous Euclidean curve.    This mode disable the *
  41. * SinglePath mode.                                  *
  42. ******************************************************************************/
  43. CagdCrvStruct *CagdAdapIsoExtract(CagdSrfStruct *Srf, CagdSrfStruct *NSrf,
  44.                   CagdSrfDirType Dir,
  45.                   CagdRType Eps, CagdBType FullIso,
  46.                   CagdBType SinglePath)
  47. {
  48.     CagdBType
  49.     SrfBezier = FALSE;
  50.     CagdRType Crv1Param, Crv2Param;
  51.     CagdCrvStruct *Crv1, *Crv2, *NCrv1, *NCrv2, *AllAdapIso, *TCrv;
  52.  
  53.     if (NSrf != NULL)
  54.     SinglePath = FALSE;
  55.  
  56.     switch (Srf -> GType) {
  57.     case CAGD_SBEZIER_TYPE:
  58.         Srf = CnvrtBezier2BsplineSrf(Srf);
  59.         SrfBezier = TRUE;
  60.         break;
  61.     case CAGD_SBSPLINE_TYPE:
  62.         break;
  63.     default:
  64.         FATAL_ERROR(CAGD_ERR_WRONG_SRF);
  65.         break;
  66.     }
  67.  
  68.     switch (Dir) {
  69.     case CAGD_CONST_U_DIR:
  70.         Crv1Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  71.         Srf -> UKnotVector[0] + EPSILON : EPSILON;
  72.         Crv2Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  73.         Srf -> UKnotVector[Srf -> ULength +
  74.                    Srf -> UOrder - 1] - EPSILON
  75.         : 1.0 - EPSILON;
  76.         break;
  77.     case CAGD_CONST_V_DIR:
  78.         Crv1Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  79.         Srf -> VKnotVector[0] + EPSILON : EPSILON;
  80.         Crv2Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  81.         Srf -> VKnotVector[Srf -> VLength +
  82.                    Srf -> VOrder - 1] - EPSILON
  83.         : 1.0 - EPSILON;
  84.         break;
  85.     default:
  86.         FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  87.         break;
  88.     }
  89.  
  90.     Crv1 = CagdCrvFromSrf(Srf, Crv1Param, Dir);
  91.     Crv2 = CagdCrvFromSrf(Srf, Crv2Param, Dir);
  92.     if (NSrf != NULL) {
  93.     NCrv1 = CagdCrvFromSrf(NSrf, Crv1Param, Dir);
  94.     NCrv2 = CagdCrvFromSrf(NSrf, Crv2Param, Dir);
  95.     }
  96.     else
  97.     NCrv1 = NCrv2 = NULL;
  98.  
  99.     /* Compute the adaptive iso curves. */
  100.     AllAdapIso = CagdAdapIsoExtractAux(0, Srf, NSrf,
  101.                        Crv1, NCrv1, Crv2, NCrv2,
  102.                        Crv1Param, Crv2Param,
  103.                        Dir, Eps * Eps, FullIso, SinglePath);
  104.  
  105.     /* Chain first and last iso curves that always span the entire domain. */
  106.     if (AllAdapIso != NULL) {
  107.     Crv1 -> Pnext = AllAdapIso;
  108.     for (TCrv = AllAdapIso; TCrv -> Pnext != NULL; TCrv = TCrv -> Pnext);
  109.     TCrv -> Pnext = Crv2;
  110.     }
  111.     else
  112.     Crv1 -> Pnext = Crv2;
  113.  
  114.     if (NSrf != NULL) {
  115.     NCrv1 -> Pnext = Crv1 -> Pnext;
  116.     Crv1 -> Pnext = NCrv1;
  117.     NCrv2 -> Pnext = Crv2 -> Pnext;
  118.     Crv2 -> Pnext = NCrv2;
  119.     }
  120.  
  121.     if (SrfBezier)
  122.     CagdSrfFree(Srf);
  123.  
  124.     return Crv1;
  125. }
  126.  
  127. /******************************************************************************
  128. * An auxiliary function of CagdAdapIsoExtract. Computes the distance square   *
  129. * between the given two curves, extract the regions that are far than that    *
  130. * and recursively invoke this function with them.                  *
  131. ******************************************************************************/
  132. static CagdCrvStruct *CagdAdapIsoExtractAux(int Level,
  133.                      CagdSrfStruct *Srf, CagdSrfStruct *NSrf,
  134.                      CagdCrvStruct *Crv1, CagdCrvStruct *NCrv1,
  135.                      CagdCrvStruct *Crv2, CagdCrvStruct *NCrv2,
  136.                      CagdRType Crv1Param, CagdRType Crv2Param,
  137.                      CagdSrfDirType Dir, CagdRType Eps2,
  138.                      CagdBType FullIso, CagdBType SinglePath)
  139. {
  140.     int i, KVLen;
  141.     CagdCrvStruct
  142.     *DiffCrv = CagdCrvSub(Crv1, Crv2),
  143.     *DistCrv2 = CagdCrvDotProd(DiffCrv, DiffCrv);  /* Dist.^2 function. */
  144.     CagdPointType
  145.     PType = DistCrv2 -> PType;
  146.     CagdRType Dist, *KV, LastT, DistCrv2Min, DistCrv2Max,
  147.     **Points, *PtsW, *PtsX, LastDist,
  148.     *Nodes = NULL;
  149.     CagdBType CloseEnough, LastCloseEnough;
  150.     CagdCrvStruct *TCrv,
  151.     *AllAdapIsoTail = NULL,
  152.     *AllAdapIso = NULL;
  153.  
  154.     CagdCrvFree(DiffCrv);
  155.  
  156.     /* Simple heuristic how much to refine DistCrv2: */
  157.     KVLen = DistCrv2 -> Length * 2;
  158.     DistCrv2Min = DistCrv2 -> KnotVector[0];
  159.     DistCrv2Max = DistCrv2 -> KnotVector[DistCrv2 -> Order +
  160.                      DistCrv2 -> Length - 1];
  161.     KV = (CagdRType *) IritMalloc(sizeof(CagdRType) * KVLen);
  162.     for (i = 0; i < KVLen; i++)
  163.     KV[i] = DistCrv2Min + (i + 1) * (DistCrv2Max - DistCrv2Min) /
  164.                                 (KVLen + 1);
  165.  
  166.     TCrv = BspCrvKnotInsertNDiff(DistCrv2, FALSE, KV, KVLen);
  167.     IritFree((VoidPtr) KV);
  168.     CagdCrvFree(DistCrv2);
  169.     DistCrv2 = TCrv;
  170.  
  171.     Nodes = BspKnotNodes(DistCrv2 -> KnotVector,
  172.              DistCrv2 -> Length + DistCrv2 -> Order,
  173.              DistCrv2 -> Order);
  174.     LastT = Nodes[0];
  175.     Points = DistCrv2 -> Points,
  176.     PtsW = Points[W],
  177.     PtsX = Points[X],
  178.     LastDist = (PType == CAGD_PT_E1_TYPE ? PtsX[0]
  179.                      : (PtsX[0] / PtsW[0])) - Eps2;
  180.     LastCloseEnough = LastDist < 0.0 && MinSubdivLevel <= Level;
  181.  
  182.     for (i = 1; i < DistCrv2 -> Length; i++) {
  183.     Dist = (PType == CAGD_PT_E1_TYPE ? PtsX[i]
  184.                      : (PtsX[i] / PtsW[i])) - Eps2;
  185.     CloseEnough = Dist < 0.0 && MinSubdivLevel <= Level;
  186.  
  187.     if (CloseEnough != LastCloseEnough ||
  188.         (i == DistCrv2 -> Length - 1 && !LastCloseEnough)) {
  189.         CagdRType t;
  190.  
  191.         if (CloseEnough == LastCloseEnough)
  192.         t = Nodes[DistCrv2 -> Length - 1];
  193.         else
  194.         CONVEX_BLEND(Nodes[i - 1], Nodes[i], LastDist, Dist, t);
  195.  
  196.         if (CloseEnough ||
  197.         (i == DistCrv2 -> Length - 1 && !LastCloseEnough)) {
  198.         /* We are at the end of a region that is not close enough. */
  199.         if (SinglePath) {
  200.             CagdRType
  201.                 MidParam1 = (Crv1Param * 2.0 + Crv2Param) / 3.0,
  202.             MidParam2 = (Crv1Param + Crv2Param * 2.0) / 3.0;
  203.             CagdCrvStruct
  204.                 *AdapIso1, *AdapIso2, *AdapIso3, *AdapIso,
  205.             *MidCrv1 = CagdCrvFromSrf(Srf, MidParam1, Dir),
  206.             *MidCrv2 = CagdCrvFromSrf(Srf, MidParam2, Dir);
  207.  
  208.             if (FullIso) {
  209.             AdapIso1 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  210.                              Crv1, NULL,
  211.                              MidCrv1, NULL,
  212.                              Crv1Param, MidParam1,
  213.                              Dir, Eps2,
  214.                              FullIso, SinglePath);
  215.             AdapIso2 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  216.                              MidCrv1, NULL,
  217.                              MidCrv2, NULL,
  218.                              MidParam1, MidParam2,
  219.                              Dir, Eps2,
  220.                              FullIso, SinglePath);
  221.             AdapIso3 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  222.                              MidCrv2, NULL,
  223.                              Crv2, NULL,
  224.                              MidParam2, Crv2Param,
  225.                              Dir, Eps2,
  226.                              FullIso, SinglePath);
  227.  
  228.             if (AdapIso1 != NULL) {
  229.                 for (TCrv = AdapIso1;
  230.                  TCrv -> Pnext != NULL;
  231.                  TCrv = TCrv -> Pnext);
  232.                 TCrv -> Pnext = MidCrv1;
  233.                 AdapIso = AdapIso1;
  234.             }
  235.             else
  236.                 AdapIso = MidCrv1; 
  237.             if (AdapIso2 != NULL)
  238.                 MidCrv1 -> Pnext = AdapIso2;
  239.  
  240.             if (AdapIso2 != NULL) {
  241.                 for (TCrv = AdapIso2;
  242.                  TCrv -> Pnext != NULL;
  243.                  TCrv = TCrv -> Pnext);
  244.                 TCrv -> Pnext = MidCrv2;
  245.             }
  246.             else
  247.                 MidCrv1 -> Pnext = MidCrv2;
  248.             if (AdapIso2 != NULL)
  249.                 MidCrv2 -> Pnext = AdapIso3;
  250.  
  251.             /* Chain these isolines to the entire set.*/
  252.             if (AllAdapIso)
  253.                 AllAdapIsoTail -> Pnext = AdapIso;
  254.             else
  255.                 AllAdapIso = AdapIso;
  256.  
  257.             for (AllAdapIsoTail = MidCrv2;
  258.                  AllAdapIsoTail -> Pnext != NULL;
  259.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  260.  
  261.             break; /* Only one (entire domain) region! */
  262.             }
  263.             else {
  264.             CagdCrvStruct *Region1, *Region2,
  265.                 *MidRegion1, *MidRegion2;
  266.  
  267.             Region1 = CagdCrvRegionFromCrv(Crv1, LastT, t),
  268.             Region2 = CagdCrvRegionFromCrv(Crv2, LastT, t);
  269.             MidRegion1 = CagdCrvRegionFromCrv(MidCrv1, LastT, t);
  270.             MidRegion2 = CagdCrvRegionFromCrv(MidCrv2, LastT, t);
  271.             CagdCrvFree(MidCrv1);
  272.             CagdCrvFree(MidCrv2);
  273.  
  274.             AdapIso1 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  275.                              Region1, NULL,
  276.                              MidRegion1, NULL,
  277.                              Crv1Param, MidParam1,
  278.                              Dir, Eps2,
  279.                              FullIso, SinglePath);
  280.             AdapIso2 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  281.                              MidRegion1, NULL,
  282.                              MidRegion2, NULL,
  283.                              MidParam1, MidParam2,
  284.                              Dir, Eps2,
  285.                              FullIso, SinglePath);
  286.             AdapIso3 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  287.                              MidRegion2, NULL,
  288.                              Region2, NULL,
  289.                              MidParam2, Crv2Param,
  290.                              Dir, Eps2,
  291.                              FullIso, SinglePath);
  292.  
  293.             if (AdapIso1 != NULL) {
  294.                 for (TCrv = AdapIso1;
  295.                  TCrv -> Pnext != NULL;
  296.                  TCrv = TCrv -> Pnext);
  297.                 TCrv -> Pnext = MidRegion1;
  298.                 AdapIso = AdapIso1;
  299.             }
  300.             else
  301.                 AdapIso = MidRegion1; 
  302.             if (AdapIso2 != NULL)
  303.                 MidRegion1 -> Pnext = AdapIso2;
  304.  
  305.             if (AdapIso2 != NULL) {
  306.                 for (TCrv = AdapIso2;
  307.                  TCrv -> Pnext != NULL;
  308.                  TCrv = TCrv -> Pnext);
  309.                 TCrv -> Pnext = MidRegion2;
  310.             }
  311.             else
  312.                 MidRegion1 -> Pnext = MidRegion2;
  313.             if (AdapIso2 != NULL)
  314.                 MidRegion2 -> Pnext = AdapIso3;
  315.  
  316.             /* Chain these isolines to the entire set.*/
  317.             if (AllAdapIso)
  318.                 AllAdapIsoTail -> Pnext = AdapIso;
  319.             else
  320.                 AllAdapIso = AdapIso;
  321.  
  322.             for (AllAdapIsoTail = MidRegion2;
  323.                  AllAdapIsoTail -> Pnext != NULL;
  324.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  325.             }
  326.         }
  327.         else { /* Return all the isocurves as a list of curves. */
  328.             CagdRType
  329.                 MidParam = (Crv1Param + Crv2Param) / 2.0;
  330.             CagdCrvStruct *AdapIso1, *AdapIso2, *AdapIso,
  331.             *MidCrv = CagdCrvFromSrf(Srf, MidParam, Dir),
  332.             *MidNCrv = NSrf ? CagdCrvFromSrf(NSrf, MidParam, Dir)
  333.                     : NULL;
  334.  
  335.             if (FullIso) {
  336.             AdapIso1 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  337.                              Crv1, NCrv1,
  338.                              MidCrv, MidNCrv,
  339.                              Crv1Param, MidParam,
  340.                              Dir, Eps2,
  341.                              FullIso, SinglePath);
  342.             AdapIso2 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  343.                              MidCrv, MidNCrv,
  344.                              Crv2, NCrv2,
  345.                              MidParam, Crv2Param,
  346.                              Dir, Eps2,
  347.                              FullIso, SinglePath);
  348.  
  349.             if (AdapIso1 != NULL) {
  350.                 for (TCrv = AdapIso1;
  351.                  TCrv -> Pnext != NULL;
  352.                  TCrv = TCrv -> Pnext);
  353.                 TCrv -> Pnext = MidCrv;
  354.                 AdapIso = AdapIso1;
  355.             }
  356.             else
  357.                 AdapIso = MidCrv;
  358.  
  359.             if (NSrf != NULL) {
  360.                 MidCrv -> Pnext = MidNCrv;
  361.                 MidCrv = MidNCrv;
  362.             }
  363.  
  364.             if (AdapIso2 != NULL)
  365.                 MidCrv -> Pnext = AdapIso2;
  366.  
  367.             /* Chain these isolines to the entire set.*/
  368.             if (AllAdapIso)
  369.                 AllAdapIsoTail -> Pnext = AdapIso;
  370.             else
  371.                 AllAdapIso = AdapIso;
  372.  
  373.             for (AllAdapIsoTail = MidCrv;
  374.                  AllAdapIsoTail -> Pnext != NULL;
  375.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  376.  
  377.             break; /* Only one (entire domain) region! */
  378.             }
  379.             else {
  380.             CagdCrvStruct *Region1, *Region2, *NRegion1, *NRegion2,
  381.                 *MidRegion, *MidNRegion;
  382.  
  383.             Region1 = CagdCrvRegionFromCrv(Crv1, LastT, t);
  384.             Region2 = CagdCrvRegionFromCrv(Crv2, LastT, t);
  385.             MidRegion = CagdCrvRegionFromCrv(MidCrv, LastT, t);
  386.             if (NSrf) {
  387.                 NRegion1 = CagdCrvRegionFromCrv(NCrv1, LastT, t);
  388.                 NRegion2 = CagdCrvRegionFromCrv(NCrv2, LastT, t);
  389.                 MidNRegion = CagdCrvRegionFromCrv(MidNCrv, LastT,
  390.                                   t);
  391.                 CagdCrvFree(MidNCrv);
  392.             }
  393.             CagdCrvFree(MidCrv);
  394.  
  395.             AdapIso1 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  396.                              Region1, NRegion1,
  397.                              MidRegion, MidNRegion,
  398.                              Crv1Param, MidParam,
  399.                              Dir, Eps2,
  400.                              FullIso, SinglePath);
  401.             AdapIso2 = CagdAdapIsoExtractAux(Level + 1, Srf, NSrf,
  402.                              MidRegion, MidNRegion,
  403.                              Region2, NRegion2,
  404.                              MidParam, Crv2Param,
  405.                              Dir, Eps2,
  406.                              FullIso, SinglePath);
  407.  
  408.             if (AdapIso1 != NULL) {
  409.                 for (TCrv = AdapIso1;
  410.                  TCrv -> Pnext != NULL;
  411.                  TCrv = TCrv -> Pnext);
  412.                 TCrv -> Pnext = MidRegion;
  413.                 AdapIso = AdapIso1;
  414.             }
  415.             else
  416.                 AdapIso = MidRegion;
  417.  
  418.             if (NSrf != NULL) {
  419.                 MidRegion -> Pnext = MidNRegion;
  420.                 MidRegion = MidNRegion;
  421.             }
  422.  
  423.             if (AdapIso2 != NULL)
  424.                 MidRegion -> Pnext = AdapIso2;
  425.  
  426.             CagdCrvFree(Region1);
  427.             CagdCrvFree(Region2);
  428.             if (NSrf != NULL) {
  429.                 CagdCrvFree(NRegion1);
  430.                 CagdCrvFree(NRegion2);
  431.             }
  432.  
  433.             /* Chain these isolines to the entire set.*/
  434.             if (AllAdapIso)
  435.                 AllAdapIsoTail -> Pnext = AdapIso;
  436.             else
  437.                 AllAdapIso = AdapIso;
  438.  
  439.             for (AllAdapIsoTail = MidRegion;
  440.                  AllAdapIsoTail -> Pnext != NULL;
  441.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  442.             }
  443.         }
  444.         }
  445.         else {
  446.         /* We are at the beginning of a region not close enough. */
  447.         LastT = t;
  448.         }
  449.     }
  450.  
  451.     LastDist = Dist;
  452.     LastCloseEnough = CloseEnough;
  453.     }
  454.  
  455.     CagdCrvFree(DistCrv2);
  456.     IritFree((VoidPtr) Nodes);
  457.  
  458.     if (SinglePath) { /* Add connecting isocurves into the existing curves. */
  459.     /* Not implemented yet. */
  460.     }
  461.  
  462.     return AllAdapIso;
  463. }
  464.